package com.gjy.leetcode.niuke;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * BM19 寻找峰值
 * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
 * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
 * 2.假设 nums[-1] =负无穷大 nums[n] =负无穷大
 * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
 * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
 *
 * @author 宫静雨
 * @version 1.0
 * @since 2023-01-31 14:15:50
 */
public class BM19 {

    /**
     * i-1 i i+1
     */
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        for (int i = 1; i < nums.length - 2; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return -1;
    }

    public int findPeakElement2(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return r;
    }

    @Test
    public void test2() {
        int[] array = {2, 4, 1, 2, 7, 8, 4};
        int peakElement = findPeakElement2(array);
        Assertions.assertEquals(1, peakElement);
    }

    @Test
    public void test1() {
        int[] array = {2, 4, 1, 2, 7, 8, 4};
        int peakElement = findPeakElement(array);
        Assertions.assertEquals(1, peakElement);
    }
}
